import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
 *
 * 示例：
 * 输入：S = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 *
 * 输入：S = "3z4"
 * 输出：["3z4", "3Z4"]
 *
 * 输入：S = "12345"
 * 输出：["12345"]
 *
 * 提示：
 * S的长度不超过12。
 * S仅由数字和字母组成。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/letter-case-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q00784m {

    private List<String> ans;

    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList<>();
        char[] cs = s.toCharArray();
        backtrace(cs, 0);
        return ans;
    }

    private void backtrace(char[] cs, int i) {
        if (i == cs.length) {
            ans.add(new String(cs));
        } else {
            backtrace(cs, i + 1); // 处理自身
            char c = cs[i];
            if (Character.isLowerCase(cs[i])){ // 小写字母
                cs[i] = Character.toUpperCase(c);
                backtrace(cs, i + 1);
                cs[i] = c;
            } else if (Character.isUpperCase(cs[i])){ // 大写字母
                cs[i] = Character.toLowerCase(c);
                backtrace(cs, i + 1);
                cs[i] = c;
            }
        }
    }
}
